Chapter 3 - Asymptotic Notations

O Big-O Notation (Omicron)

• possibly asymptotically tight upper bound for f(n) - Cannot do worse, can do better
  

• n is the problem size.
  

• f(n) ∈ O(g(n)) where:

O(g(n)) = { h(n): ∃ positive constants c, n0 such that 0 ≤ h(n) ≤ cg(n), ∀ n ≥ n0}

Meaning for all values of n ≥ n₀ h(n) is on or below g(n).

• O(g(n)) is a set of all the functions h(n) that are less than or equal to cg(n), ∀ n ≥ n₀.
  

If f(n) ≤ cg(n),  c > 0, ∀ n ≥ n0 then f(n) ∈ O(g(n))

meaning f(n) is one of the h(n)'s in the set

and g(n) is an asymptotically tight upper bound for f(n).

We usually write: f(n) = O(g(n))

• Expressed as limits:

  O  f(n) / g(n) = c for some 0 ≤ c < ∞

  n³ / n² = n = ∞                                  n³ ≠ O(n²)

  n²+n / n² = 1 + 1/n = 1                      n²+n = O(n²)

Example - functions in O(n²)

n   n/1000    n^1.9    n²     n²+n        1000n²+50n

Example - functions not in O(n²)

n³       n^2.1       2ⁿ

 

Question 3.2 - Show using limits.

1. 1000n²+50n = O(n²)
   
   
2. n³/1000 ≠ O(n²)

 

Question 3.3 - Which functions are in O(n²)?

n^1/2    n²      n²+n²+n²       n³        n^2.1

 

If f(n) ≤ cg(n),  c > 0, ∀ n ≥ n0 then f(n) ∈ O(g(n))

Example      Show    2n² = O(n³)

0 ≤ h(n) ≤ cg(n)                  Definition of O(g(n))

0 ≤ 2n² ≤ cn³                      Substitute

0/n³ ≤ 2n²/n³ ≤ cn³/n³       Divide by n³

Determine c

0 ≤ 2/n ≤ c                         2/n = 0
                                           2/n maximum when n=1

0 ≤ 2/1 ≤ c = 2                   Satisfied by c=2

Determine n₀

0 ≤ 2/n₀ ≤ 2                     

0 ≤ 2/2 ≤ n₀

0 ≤ 1 ≤ n₀ = 1                    and n₀=1

0 ≤ 2n² ≤ 2n³                     ∀ n ≥ n₀=1

 

Example - 1000n² + 50n = O(n²) 

0 ≤ h(n) ≤ cg(n)
0 ≤ 1000n2 + 50n ≤ cn2
0/n2 ≤ 1000n2/n2 + 50n/n2 ≤ cn2/n2		Divide by n2
0 ≤ 1000 + 50/n ≤ c		Note that 50/n → 0 as n → ∞ Greatest when n = 1
0 ≤ 1000 + 50/1 = 1050 ≤ c = 1050		With c=1050
0 ≤ 1000 + 50/n0 ≤ 1050		Find n0
-1000 ≤ 50/n0 ≤ 50
-20 ≤ 1/n0 ≤ 1
-20n0 ≤ 1 ≤ n0 = 1		n0=1
0 ≤ 1000n2 + 50n ≤ 1050n2		∀ n ≥ n0=1, c=1050

If f(n) ≤ cg(n),  c > 0, ∀ n ≥ n0 then f(n) ∈ O(g(n))

Question 3.4.1 - Show that 2n²+n is in O(n²) by finding c and n₀

 

Example - n² + 50n = O(n²) 

0 ≤ h(n) ≤ cg(n)
0 ≤ n2 + 50n ≤ cn2
0/n2 ≤ n2/n2 + 50n/n2 ≤ cn2/n2		Divide by n2
0 ≤ 1 + 50/n ≤ c		Note that 50/n → 0 as n → ∞ Pick n = 50
0 ≤ 1 + 50/50 = 2 ≤ c = 2		With c=2
0 ≤ 1 + 50/n0 ≤ 2		Find n0
-1 ≤ 50/n0 ≤ 1
-20n0 ≤ 50 ≤ n0 = 50		n0=50
0 ≤ n2 + 50n ≤ 2n2		∀ n ≥ n0=50, c=2

 

Example - n = O(n lg n) 

0 ≤ h(n) ≤ cg(n)
0 ≤ n ≤ cn lg n
0/n lg n ≤ n/n lg n ≤ cn lg n/n lg n		Divide by n lg n
0 ≤ 1/lg n ≤ c		Note that 1/lg n → 0 as n → ∞ Greatest when n = 2
0 ≤ 1/lg 21 = 1 ≤ c = 1		With c=1
0 ≤ 1/lg n0 ≤ c = 1		Find n0
0 ≤ 1/lg n0 ≤ 1
0 ≤ 1 ≤ lg n0 = 1		lg n0 = 1 when n0=21=2
0 ≤ n ≤ cn lg n		∀ n ≥ n0=2, c=1

Example - n²+n²+n² = 3n² = O(n³)

0 ≤ h(n) ≤ cg(n)    

0 ≤ 3n² ≤ cn³                               Guessing c and n₀

0 ≤ 3*2² = 12 ≤ 1*2³ = 8            with c=1 and n₀=2 fails to hold

0 ≤ 3*2² = 12 ≤ 2*2³ = 16          with c=2 and n₀=2

0 ≤ 3*3² = 27 ≤ 1*3³ = 81          with c=1 and n₀=3

Determining c and n₀

0 ≤ h(n) ≤ cg(n)    

0 ≤ 3n² ≤ cn³

0/n³ ≤ 3n²/n³ ≤ cn³/n³

0 ≤ 3/n ≤ c                                  Find c=3 when n=1

                                                   because 3/n → 0 as n → ∞, maximum when n=1

                                                   3/n only grows smaller as n → ∞

0 ≤ 3/n₀ ≤ 3                                Find n₀ with c=3

0 ≤ 1/n₀ ≤ 1                              

0 ≤ 1 ≤ n₀ = 1                            n₀ = 1

0 ≤ 3n² ≤  3n³                            ∀ n ≥ n₀=1

If f(n) ≤ cg(n),  c > 0, ∀ n ≥ n0 then f(n) ∈ O(g(n))

Question 3.4.2 - Show that lg n is in O(n) by finding c and n₀

Question 3.4.3 - Verify that for a>0, b>0 any linear function an+b = O(n²)  by finding c and n₀.

 

Example - n³ ≠ O(n²)

0 ≤ h(n) ≤ cg(n)    

0 ≤ n³ ≤ cn²

0/n² ≤ n³/n² ≤ cn²/n²

0 ≤ n ≤ c                                     because n → ∞, no c exists where ∀ n ≥ n₀ true

Example - 5n³+10n ≠ O(n²)

0 ≤ h(n) ≤ cg(n)    

5n³+10n ≤ cn²

5n³/n² + 10n/n² ≤ cn²/n²

5n + 10/n ≤ c

(5n² + 10)/n ≤ c                          because (5n² + 10)/n → ∞,
                                                   no c exists where ∀ n ≥ n₀ true

Question 3.5 - Show 2n³+n ≠ O(n²)

 

n² bounded above by n^2.1

n² bounded below by n^1.9

1000n² + 50n = O(n²) 

with c=1050 and n₀=1

Graph illustrates that:

0 ≤ 1000n² + 50n ≤ 1050n²

Note that the y-scale is much greater than the x-scale.

n² + 50n = O(n²)   

with c=2 and n₀=50

n = O(n lg n) 

with c=1 and n₀=2

3n² = O(n³) 

with c=1 and n₀=2 fails

with c=1 and n₀=3 holds

 

 

 

possibly asymptotically tight lower bound for f(n) - Cannot do better, can do worse

f(n) ∈ Ω(g(n)) where:

Ω(g(n)) = {h(n): ∃ positive constants c > 0, n0 such that 0 ≤ cg(n) ≤ h(n), ∀ n ≥ n0}

Meaning for all values of n ≥ n₀ h(n) is on or above g(n).

Ω(g(n)) is a set of all the functions h(n) that are greater than or equal cg(n), ∀ n ≥ n₀.

If cg(n) ≤ f(n), c > 0 and ∀ n ≥ n0, then f(n) ∈ Ω(g(n))

meaning f(n) is one of the h(n)'s in the set

and g(n) is an asymptotically tight lower bound for f(n).

Expressed as limits:

Ω  f(n) / g(n) = c for some 0 < c ≤ ∞

n³ / n² = n = ∞                               n³ = Ω(n²)

n / n² = 1/n = 0                               n ≠ Ω(n²)

 

Example - functions in Ω(n)

n    n/1000     n^1.999    n²     n²+n      1000n²+50n

Example - functions not in Ω(n²)

n       n^{1.999       v} n

Question 3.6.1 - Show using limits:

1. 1/n ≠ Ω(n²)
   
   
2. n²/1000 = Ω(n²)

 

Example - n³ = Ω(n²)  with c=1 and n₀=1

0 ≤ cg(n) ≤ h(n)    

0 ≤ 1*1² = 1 ≤ 1 = 1³    

0 ≤ cg(n) ≤ h(n)
0 ≤ cn2 ≤ n3
0/n2 ≤ cn2/n2 ≤ n3/n2
0 ≤ c ≤ n
0 ≤ 1 ≤ 1	with c=1 and n0=1 since n increases. n = ∞

Question 3.6.2 - Can we use n₀=0?

 

Ω(g(n)) = {h(n): ∃ positive constants c > 0, n0 such that 0 ≤ cg(n) ≤ h(n), ∀ n ≥ n0}

Example - 3n² + n = Ω(n²)

0 ≤ cg(n) ≤ h(n)
0 ≤ cn2 ≤ 3n2 + n
0/n2 ≤ cn2/n2 ≤ 3n2/n2 + n/n2
0 ≤ c ≤ 3 + 1/n	3+1/n = 3
0 ≤ c ≤ 3	c = 3
0 ≤ 3 ≤ 3 + 1/n0
-3 ≤ 3-3 ≤ 3-3 + 1/n0
-3 ≤ 0 ≤ 1/n0	n0=1 satisfies
	1/n = 0

Question 3.6.3 - From the two graphs at right, is

c=3 and n₀=1 or

c=1 and n₀=1

the better choice for 3n² + n = Ω(n²)?

Why?

 

Example - ^v n = Ω(lg n)

0 ≤ cg(n) ≤ h(n)  

0 ≤ c lg n ≤  ^v n                 

0 ≤ c lg 16 ≤  ^v 16                n₀ = 16

0 ≤ c 4 ≤ 4                          lg 2⁴  = 4 = ^v 16

0 ≤ c  ≤ 1                            c = 1

 

Question 3.7 - How does the graph indicate that this is true for n ≥ n₀ = 16?

^v n   ^{/ lg n}  = ?                            See graph at right.

If cg(n) ≤ f(n), c > 0, ∀ n ≥ n0, then f(n) ∈ Ω(g(n))

Ω  f(n) / g(n) = c for some 0 < c ≤ ∞

 

Question 3.8 - Which functions are in Ω(n²)?

n^1/2     n²      n²+n²+n²       n!      n³      n^2.1       n^1.999

Question 3.9.1 - Show that 2n²+n is in Ω(n²)

What are c and n₀?

Example - n ≠ Ω(n²)

0 ≤ cg(n) ≤ h(n)

0 ≤ cn2 ≤ n

0/n2 ≤ cn2/n2 ≤ n/n2

0 ≤ c ≤ 1/n

c depends on n and there is no n0 that satisfies as n increases.             Only c = 0 would satisfy but not allowed by definition.

1 / n = 0

Example - 3n + 5 ≠ Ω(n²)

0 ≤ cg(n) ≤ h(n)

0 ≤ cn2 ≤ 3n + 5

0/n2 ≤ cn2/n2 ≤ 3n/n2 + 5/n2

0 ≤ c ≤ 3/n + 5/n2

c depends on n and there is no n0 that satisfies as n increases.             Only c = 0 would satisfy but not allowed by definition.

3/n + 5/n2 = 0

Question 3.9.2 - Show that 2n²+n ≠ Ω(n³)

If cg(n) ≤ f(n), c > 0, ∀ n ≥ n0, then f(n) ∈ Ω(g(n))

n³ = Ω(n²)

with c=1 and n₀=1

3n² + n = Ω(n²) with c=1 and n₀=1

3n² + n = Ω(n²) with c=3 and n₀=1

^v n = Ω(lg n) with c=1 and n₀=16

asymptotically tight bound for f(n)

f(n) ∈ Θ(g(n)) where

Θ(g(n)) =      {h(n): ∃ positive constants c1, c2, n0 such that       0 ≤ c1g(n) ≤ h(n) ≤ c2g(n), ∀ n ≥ n0}

• Positive means greater than 0.
  

• Θ(g(n)) is a set of all the functions h(n) that are between c₁g(n) and c₂g(n), ∀ n ≥ n₀.
  

• If f(n) is between c₁g(n) and c₂g(n), ∀ n ≥ n₀, then f(n) ∈ Θ(g(n)),
       meaning f(n) is one of the h(n)'s in the set,
       and g(n) is an asymptotically tight bound for f(n).
  

• Expressed as limits:

  Θ f(n) / g(n) = c for some 0 < c < ∞

  n²+n / n² = 1 + 1/n = 1

Example -  n²/2-2n = Θ(n²)

c₁g(n) ≤ h(n) ≤ c₂g(n)

c₁n² ≤ n²/2-2n ≤ c₂n²

c₁n²/n² ≤ n²/2n²-2n/n² ≤ c₂n²/n²          Divide by n²

c₁ ≤ 1/2-2/n ≤ c₂

O: Determine c₂ = ½                             

• ½-2/n ≤ c₂ = ½                               ½-2/n = ½
                                                          maximum of ½-2/n

Ω: Determine c₁ = 1/10

• 0 < c₁ ≤ 1/2-2/n                              0 < c₁ minimum when n=5
• 0 < c₁ ≤ 1/2-2/5
• 0 < c₁ ≤ 5/10-4/10 = 1/10

n₀ : Determine n₀ = 5

• 1/10 ≤ 1/2-2/n₀ ≤ 1/2
• 1/10 ≤ 1/2-2/n₀ ≤ 1/2
• 2/n₀ ≤ 1/2-1/10 ≤ 1/2
• 2/n₀ ≤ 4/10 ≤ 1/2
• 2/n₀ ≤ 2/5 ≤ 1/2
• n₀ ≥ 5                                             n₀ = 5 satisfies                         

Verify

c₁n² ≤ n²/2-2n ≤ c₂n²                           with c₁=1/10, c₂=½ and n₀=5

1/10*5² ≤ 5²/2-2*5 ≤ ½*5²

25/10 ≤ 25/2-20/2 ≤ 25/2

5/2 ≤ 5/2 ≤ 25/2                                   Holds

In general: 1/10n² ≤ n²/2-2n ≤ ½n² for n ≥ 5

 

Question 3.10 - Does the following hold for ∀n ≥ n₀?

c₁n² ≤ n²/2-2n ≤ c₂n²                           with c₁=1/2, c₂=1/2 and n₀=5

 

Example - Show that ½n² - 3n ∈ Θ(n²)

• Determine ∃ c₁, c₂, n₀ positive constants such that:

  c₁n² ≤ ½n² - 3n ≤ c₂n² 

  c₁ ≤ ½ - 3/n ≤ c₂                                  Divide by n²
  

• O: Determine c₂ = ½

  ½ - 3/n ≤ c₂

  • as n → ∞, 3/n → 0
  •       ½ - 3/n = ½
  • therefore ½ ≤ c₂ or c₂ = ½               ½ - 3/n maximum for as n → ∞
    
    
• Ω: Determine c₁ = 1/14

  0 < c₁ ≤ ½ - 3/n                                      ½ - 3/n > 0 minimum for n₀ = 7

  0 < c₁ = ½ - 3/7 = 7/14 - 6/14 = 1/14     
  
  

• Determine n₀ = 7

  c₁ ≤ ½ - 3/n₀  

  1/14 ≤ ½ - 3/n₀  

  3/n₀ ≤ ½ - 1/14 = 6/14

  1/n₀ ≤ 2/14

  7 = 14/2 ≤ n₀

  n₀ ≥ 7

½n² - 3n ∈ Θ(n²) when c₁ = 1/14, c₂ = ½ and  n₀ = 7

Example - Recall we found a closed-end equation for the InsertionSort of T(n) = an² + bn + c.

a, b and c are > 0.

How do we know that? These constants are based on instruction execution counts.

Show: T(n) = an² + bn + c = Θ(n²)

c₁g(n) ≤ h(n) ≤ c₂g(n)

c₁n² ≤ an² + bn + c ≤ c₂n²

c₁n²/n² ≤ an²/n² + bn/n² + c/n² ≤ c₂n²/n²

c₁ ≤ a + b/n + c/n² ≤ c₂       

as n → ∞, b/n, c/n² → 0

a + b/n + c/n² greatest when n₀ = 1

c₁ ≤ a + b + c when c₁ = a

a + b + c ≤ c₂ when c₂ = a + b + c

Question 3.12 - (Levitin page 56)

Show that ½(n² - n) ∈ Θ(n²)

n²/2-2n = Θ(n²) 
    c₁=1/10, c₂=1/2 and n₀=5

½n²-3n = Θ(n²) 
    c₁=1/14, c₂=1/2 and n₀=7

• best case Ω - describes a lower bound for all input (it can't get any better than this).

  Example: the array is already correctly sorted.
  
  

• worst case Ω - describes a lower bound for worst case input, possibly greater than best case.

  Example: the array is sorted in reverse order.
  
  

• just Ω - same as best case Ω
  

   with c=1 and n₀=16

• best case O - describes an upper bound for best case input, possibly lower than worst case.

  Example: the array is already correctly sorted.
  
  

• worst case O - describes an upper bound for all input (it can't get any worse than this).

  Example: the array is sorted in reverse order.
  
  

• just O - same as worst case O

   with c=1 and n₀=2

• best case Θ - not used
  
  
• worst case Θ - describes asymptotic bounds for worst case input
  
  
• just Θ - same as worst case Θ